/*
 * @lc app=leetcode.cn id=767 lang=javascript
 *
 * [767] 重构字符串
 */

// @lc code=start
/**
 * @param {string} S
 * @return {string}
 */
var reorganizeString = function(S) {
    let arr = new Array(26).fill(0)
    for (let s of S) {
        let i = s.charCodeAt() - 97
        arr[i] = (arr[i] || [s, 0])
        arr[i][1] += 1
    }
    let re = arr.filter(item => item != 0)
    re.sort((a,b)=>b[1]-a[1])

    if (re[0][1] > ((S.length+1) >> 1)) return ""

    let i = 0, k = 0, ans = new Array(S.length)
    for (let j = 0, p = 0; j < S.length; j++) {
       ans[i] = re[p][0]
       i += 2
       if (i >= S.length) i = 1
       if (++k >= re[p][1]) {
           k = 0
           p++
       }
    }
    return ans.join('')
};
// @lc code=end

reorganizeString("aab")